/*************************************************************************
	> File Name: 002.ac.cpp
	> Author: Maureen 
	> Mail: Maureen@qq.com 
	> Created Time: 三  2/24 19:13:26 2021
 ************************************************************************/

#include <iostream>
using namespace std;
#define BASE 26
typedef struct Node {
    int flag;
    int tag[BASE]; //标记是否为原字典树上的边 Trie:1 AC:0
    const char *str;
    struct Node *next[BASE];
    struct Node *fail;
} Node;

Node *getNewNode() {
    Node *p = (Node *)malloc(sizeof(Node));
    p->flag = 0;
    memset(p->next, 0, sizeof(p->next));
    p->fail = NULL;
    return p;
}

//建立字典树
void insert(Node *root, const char *str) {
    for (int i = 0; str[i]; i++) {
        int ind = str[i] - 'a';
        if (root->next[ind] == NULL) root->next[ind] = getNewNode();
        root->tag[ind] = 1; //标记该节点的ind这条边为原生的
        root = root->next[ind];
    }
    root->flag = 1;
    root->str = strdup(str);
    return ;
}

void build_ac(Node *root) {
   Node **q = (Node **)malloc(sizeof(Node *));
    int head = 0, tail = 0;
    root->fail = NULL;
    for (int i = 0; i < BASE; i++) {
        if (root->next[i] == NULL) {
            root->next[i] = root;
            continue;
        }
        root->next[i]->fail = root;
        q[tail++] = root->next[i];
    }
    while (head < tail) {
        Node *p = q[head++];
        for (int i = 0; i < BASE; i++) {
            Node *c = p->next[i], *k = p->fail;
            if (c == NULL) {
                //路径压缩：i孩子为空，则将该指针指向其等价匹配节点的非空孩子
                p->next[i] = k->next[i];
                continue;
            }
            //因为针对所有的next空指针的情况作了处理，所以k不会是空指针
            k = k->next[i];
            c->fail = k;
            q[tail++] = c;
        }
    }
    free(q);
    return ;
}

void match(Node *root, const char *text) {
    Node *p = root, *q;
    for (int i = 0; text[i]; i++) {
        cout << "input : " << text[i] << endl;
        int ind = text[i] - 'a';
        //本来应该是每个状态进行跳转，但是从宏观上看就是直接找到了目标节点
        p = p->next[ind];
        q = p;
        while (q) {
            if (q->flag) cout << "find : " << q->str << endl;
            q = q->fail;
        }
    }
    return ;
} 

void clear(Node *root) {
    if (root == NULL) return ;
    for (int i = 0; i < BASE; i++) {
        //因为在创建fail指针的过程中建立了一些不属于原来字典树的边，不是单纯的树了，更像是图，所以要区分哪些是原来字典树的边
        if (root->tag[i]) clear(root->next[i]);
    }
    free(root);
    return ;
}

int main() {
    int n;
    scanf("%d", &n);
    char str[100];
    Node *root = getNewNode();
    for (int i = 0; i < n; i++) {
        scanf("%s", str);
        insert(root, str);
    }
    build_ac(root);
    scanf("%s", str);
    match(root, str);
    return 0;
}
